import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class TestDemo5B {

    public static void Swap(char[] str, int i, int j) {
        char temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }

    public static boolean IsExist(ArrayList<String> result, char[] str) {
        return result.contains(String.valueOf(str));
    }

    public static void PermutationHelper(char[] str, int start, ArrayList<String> result) {
        if (start == str.length - 1) {
            if (!IsExist(result, str)) {
                result.add(new String(str));
            }
            return;
        }
        for (int i = start; i < str.length; i++) {
            Swap(str, start, i);
            PermutationHelper(str, start + 1, result);
            Swap(str, start, i);
        }
    }

    public static ArrayList<String> Permutation(String str) {
        ArrayList<String> result = new ArrayList<>();
        if (str != null && str.length() > 0) {
            PermutationHelper(str.toCharArray(), 0, result);
            Collections.sort(result);
        }
        return result;
    }

    public static void main3(String[] args) {
        String str = "abc";
        ArrayList<String> str1 = Permutation(str);
        System.out.println(str1);
    }

    public int removeDuplicates(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int tmp = 0;
        for (Integer num : nums) {
            if (set.add(num)) {
                nums[tmp++] = num;
            }
        }
        return tmp;
    }

    public static void sum(int[] array, int target) {
        int[] result = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            map.put(array[i], i);
        }
        int j = 0;
        for (int i = 0; i < array.length; i++) {
            if (map.containsKey(target - array[i]) && map.get(target - array[i]) != array[i]) {
                result[j] = i;
                j++;
            }
        }
    }

    public static void main1(String[] args) {
        int[] array = {2, 7, 11, 15};
        int[] result = new int[2];
        int target = 9;
        sum(array, target);
        for (int i = 0; i < 2; i++) {
            System.out.println(result);
        }
    }

    //合并 两个有序数组(方法一)
    //定义一个新数组,两个数组依次比较,小的放到新数组里面
    public void merge1(int[] nums1, int m, int[] nums2, int n){
        int k=m+n;
        int []tmp=new int [k];
        for(int i=0, num1Index=0,num2Index=0;i<k;i++){
            if(m>=num1Index){//如果m数组遍历完,直接把n的数组全部放到新数组里面
                tmp[i]=nums2[num2Index++];
            }else if(n>=num2Index){
                tmp[i]=nums1[num1Index++];
                //nums1和nums2比较小的放到新数组里面
            }else if(nums1[num1Index]>nums2[num2Index]){
                tmp[i]=nums2[num2Index++];
            }else {
                tmp[i]=nums1[num1Index++];
            }
        }
        for(int i=0;i<k;i++){
            nums1[i]=tmp[i];
        }
    }
    //合并两个有序数组(方法二)
    public void merge2(int[] nums1, int m, int[] nums2, int n){
        int k=m+n;
        for(int i=k-1,num1Index=m-1,num2Index=n-1;i>=0;i--){
            if(num1Index<0){//nums1已经取完了,直接取nums2的值
                nums1[i]=nums2[num2Index--];
            }else if(num2Index<0){//nums2的值取完了,直接就遍历完了
                break;
                //nums1和nums2那个值大那个放到在后面
            }else if(nums1[num1Index]<nums2[num2Index]){
                nums1[i]=nums2[num2Index--];
            }else{
                nums1[i]=nums1[num1Index--];
            }
        }
    }

    //移动零
    //定义两个指针,从起始位置开始,i向后移到,不等于0就赋值给j,j向后移到一格.
    //i遍历完之后.从j下标之后的都赋值0
    public static void moveZeroes(int[] nums) {
        int j=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]!=0){
                nums[j++]=nums[i];
            }
        }
        for(int i=j;i<nums.length;++i){
            nums[i]=0;
        }
    }

    // 找到所有数组中消失的数字
    public static List<Integer> findDisappearedNumbers(int[] nums) {
        int n=nums.length;
        for(int x:nums){
            int tmp=(x-1)%n;//要有取模的操作,不加会报错(可能取的值超过数组的长度)
            nums[tmp]+=n;
        }
        ArrayList<Integer>result=new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            if(nums[i]<=n){//对每个数进行遍历,只要小于n说明该下标的值没有加过
                result.add(i+1);//故说明该值没有出现过
            }
        }
        return result;
    }

    public static void main2(String[] args) {
        int []nums={4,3,2,7,8,2,3,1};
        System.out.println(findDisappearedNumbers(nums));
    }

    public static void main4(String[]args){
        int n=100;
        boolean[]tmp=new boolean[100];//素数是false(初始化时为false)
        int count=0;
        for(int i=2;i<n;i++){
            if(!tmp[i]){
                count++;
                for(int j=i*i;j<n;j+=i){
                    tmp[j]=true;
                }
            }
        }
        System.out.println(count);
    }

    public static void main5(String[] args) {
        int n=100;
        int count=0;
        for(int i=2;i<n;i++){
           count+=issu(i)?1:0;
        }
        System.out.println(count);

    }
    public static boolean issu(int x){
        for(int j=2;j*j<x;j++){
            if(x%j==0){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int left=0;
        int right=2147395599;
        int index=-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(mid*mid<=2147395599){
                index=mid;
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        System.out.println(index);
    }
}





